\section{Subquadratic time offline token-forwarding algorithms}
\label{sec:centralized}
In this section, we give two centralized algorithms for the $k$-gossip
problem in the offline model. We present an $O(\min\{n^{1.5}\sqrt{\log
  n}, nk\})$ round algorithm in Section \ref{sec:upper}. Then we
present a bicriteria $\rb{O(n^\epsilon), \log n}$-approximation
algorithm in Section \ref{sec:approx}, which means if $L$ is the
number of rounds needed by an optimal algorithm where one token is
broadcast by every node per round, then our approximation algorithm
will complete in $O(n^\epsilon L)$ rounds and the number of tokens
broadcast by any node is $O(\log n)$ in any given round. Both of these
algorithms uses a directed capacitated leveled graph constructed from
the sequence of communication graphs which we call the {\em evolution
  graph}.

\smallskip
\noindent
{\em Evolution graph}: Let $V$ be the set of nodes. Consider a dynamic
network of $l$ rounds numbered $1$ through $l$ and let $G_i$ be the
communication graph for round $i$. The evolution graph for this
network is a directed capacitated graph $G$ with $2l+1$ levels
constructed as follows. We create $2l+1$ copies of $V$ and call them
$V_0, V_2, \dots, V_{2l}$. $V_i$ is the set of nodes at level $i$ and
for each node $v$ in $V$, we call its copy in $V_i$ as $v_i$. For $i =
1, \ldots, l$, level $2i-1$ corresponds to the beginning of round $i$
and level $2i$ corresponds to the end of round $i$. Level $0$
corresponds to the network at the start. Note that the end of a
particular round and the start of the next round are represented by
different levels. There are three kinds of edges in the graph. First,
for every round $i$ and every edge $(u,v) \in G_i$, we place two
directed edges with unit capacity each, one from $u_{2i-1}$ to
$v_{2i}$ and another from $v_{2i-1}$ to $u_{2i}$. We call these edges
{\em broadcast edges} as they will correspond to broadcasting of
tokens; the unit capacity on each such edge will ensure that only one
token can be sent from a node to a neighbor in one round. Second, for
every node $v$ in $V$ and every round $i$, we place an edge with
infinite capacity from $v_{2(i-1)}$ to $v_{2i}$. We call these edges
{\em buffer edges} as they ensure tokens can be stored at a node from
the end of one round to the end of the next. Finally, for every node
$v \in V$ and every round $i$, we also place an edge with unit
capacity from $v_{2(i-1)}$ to $v_{2i-1}$. We call these edges as {\em
  selection edges} as they correspond to every node selecting a token
out of those it has to broadcast in round $i$; the unit capacity
ensures that in a given round a node must send the same token to all
its neighbors. Figure \ref{fig:evolution} illustrates our
construction, and Lemma~\ref{lem:level.steiner} (moved to the appendix
due to space constraints) explains its usefulness.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{./figures/level.jpg}
\caption{An example of how to construct the evolution graph from a
  sequence of communication graphs.}
\label{fig:evolution}
\end{center}
\end{figure}


\junk{
\begin{lemma}
\label{lem:level.steiner}
Let $L$ be the number of rounds needed to solves $k$-dissemination
problem given a sequence of communication graphs. Leveled graph $G$ is
constructed from level $0$ to level $L$. Then $k$-token dissemination
problem can be solved in $L$ rounds if and only if there are $k$
directed edge-disjoint (w.r.t. capacities) Steiner trees from $k$
token sources in level $0$ to terminal set $V_L$.
\end{lemma}}



\input{flow_based}
\input{approx}
